Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» ЗВІТ до лабораторної роботи № 7 з дисципліни «Програмування складних алгоритмів» Тема «. Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів» Варіант № 24 Дата «20» червня 2022  1.1 Завдання до лабораторної роботи: 1. сформулювати математичну постановку задачі; 2. обрати метод розв’язання задачі, якщо це необхідно; 3. розробити графічну схему алгоритму; 4. записати розроблений алгоритм мовою програмування; 5. представити звіт до роботи Варіант завдання: / 1.2 Теоретичні відомості Дерево – це структура даних, що являє собою сукупність елементів і відносин, що утворюють ієрархічну структуру цих елементів. Кожен елемент дерева називається вершиною (вузлом) дерева. Вершини дерева з’єднані спрямованими дугами, які називають гілками дерева. Початковий вузол дерева називають коренем дерева, йому відповідає нульовий рівень. Листями дерева називають вершини, в які входить одна гілка і не виходить жодної гілки. Кожне дерево має такі властивості: 1) існує вузол, в який не входить ні одна дуга (корінь); 2) у кожну вершину, крім кореня, входить одна дуга. Дерева особливо часто використовують на практиці при зображенні різних ієрархій Бінарні дерева є деревами зі ступенем не більше двох. Бінарне (двійкове) дерево − це динамічна структура даних, що являє собою дерево, в якому кожна вершина має не більше двох нащадків. Таким чином, бінарне дерево складається з елементів, кожен з яких містить інформаційне поле і не більше двох посилань на різні бінарні піддерева. На кожен елемент дерева є рівно одне посилання. Кожна вершина бінарного дерева є структурою, що складається з чотирьох видів полів. Вмістом цих полів будуть відповідно: • інформаційне поле (ключ вершини); • службове поле (їх може бути декілька або жодного); • покажчик на ліве піддерево; • покажчик на праве піддерево 1.3. Результати роботи Було створено програму для запису чисел у вигляді бінарного дерева. На екран виводяться: елементи дерева, сума елементів, їх середнє арифметичне, і листи дерева, що мають непарні значення. 1.4. Лістинг програми #include <malloc.h>#include <stdio.h>#include <stdlib.h>//Бінарне деревоtypedef struct tree { int key; struct tree *left; struct tree *right;} tree_t;tree_t *tree_insert(tree_t **tr, int key);void tree_clear(tree_t *tr);//Прямий обхід дереваvoid tree_out_width(const tree_t *tr, int *u, double *counter) { if (tr == NULL) return; printf("%d ", tr->key); // Спосіб визначення суми з викор. вказівника *u = (*u) + tr->key; (*counter)++; tree_out_width(tr->left, u, counter); //За допомогою рекурсії відвідуємо ліве піддерево tree_out_width(tr->right, u, counter); //За допомогою рекурсії відвідуємо праве піддерево}void tree_out_2(const tree_t *tr) { if (tr == NULL) return; if (tr->left == NULL & tr->right == NULL & tr->key % 2 != 0) { printf("%d ", tr->key); } tree_out_2(tr->left); //За допомогою рекурсії відвідуємо ліве піддерево tree_out_2(tr->right); //За допомогою рекурсії відвідуємо праве піддерево}int main(void) { int i; tree_t *tr = NULL; srand(time(NULL)); for (i = 0; i < 10; ++i) tree_insert(&tr, rand() % 10); int sum = 0; int *poi = &sum; double coun = 0; double *pcoun = &coun; printf("Бінарне дерево: "); tree_out_width(tr, poi, pcoun); printf("\nСума елементів дерева: %d ", *poi); printf("\nСереднє арифметичне елементів дерева: %.2f", (*poi) / (*pcoun)); // tree_clear(tr); printf("\nЛисти дерева, що мають непарні значення: "); tree_out_2(tr); printf("\n"); return 0;}//вставкаtree_t *tree_insert(tree_t **tr, int key) { tree_t *p = *tr; while (p != NULL) { if (key == p->key) //дубліка...